#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
class Solution
{
public:
    int dis[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    vector<vector<bool>> visited, storemap;
    void init(vector<vector<char>> &board)
    {
        if (visited.size() == 0)
        {
            storemap.resize(board.size());
            for (int i = 0; i < storemap.size(); ++i)
            {
                storemap[i].resize(board[i].size());
            }
        }
        visited = storemap;
    }
    bool dfs(vector<vector<char>> &board, string &word, int cur, int i, int j)
    {
        if (cur >= word.size())
            return true;
        if (word[cur] != board[i][j] || visited[i][j] == true)
            return false;
        visited[i][j] = true;
        int x = i, y = j, cnt = 0;
        bool ret = false;
        for (int p = 0; p < 4; ++p)
        {
            x = i + dis[p][0];
            y = j + dis[p][1];
            if (x < 0 || y >= board[0].size() || y < 0 || x >= board.size())
            {
                cnt++;
                continue;
            }
            ret = ret || dfs(board, word, cur + 1, x, y);
            visited[x][y] = false;
        }
        if (cnt == 4 && cur >= (word.size() - 1))
            return true;
        return ret;
    }
    bool exist(vector<vector<char>> &board, string word)
    {
        if (word.size() <= 0)
            return true;
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                if (board[i][j] == word[0])
                {
                    init(board);
                    if (dfs(board, word, 0, i, j) == true)
                        return true;
                }
            }
        }
        return false;
    }
};
int main()
{
    Solution slover;
    string word = "aa";
    vector<vector<char>> board = {{'a', 'a'}};
    if (slover.exist(board, word))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}